1. Field of the Invention
The present invention relates to basis conversion in a finite field GF(2n). More particularly, the present invention relates to an apparatus and method for basis conversion between a standard representation on a standard basis and a dual representation on a dual basis.
2. Description of the Related Art
A finite field GF(2n) is a number system including 2n elements. Based on the fact that each element of a finite field can be represented with n bits, practical applications of the finite field may be accomplished. Practical applications, such as error correction codes and implementation of an elliptic curve cryptosystem in hardware, frequently use calculations in GF(2n). An apparatus for coding/decoding Reed-Solomon codes is required to perform calculations in GF(2n), and an encryption/decryption apparatus of an elliptic curve cryptosystem is required to perform calculations in GF(2n), where “n” is a large value.
A finite field GF(2) is a number system having addition and multiplication rules defined by Formula (1) and having only binary numbers 0 and 1 as its elements.0+0=1+1=00+1=1+0=10×0=1×0=0×1=01×1=1   (1)
Here, the addition is an XOR (exclusive OR) operation, and the multiplication is an AND operation.
The finite field GF(2n) (where n>1) is a number system including 2n elements. In this number system, addition and multiplication correspond to arithmetic modulo with respect to an irreducible n-degree polynomial having coefficients in GF(2). The irreducible n-degree polynomial is referred to as a defining polynomial. When a root of the defining polynomial is represented with α, an element of the finite field has a standard representation defined by Formula (2).a0+a1α+a2α2+ . . . +an−1αn−1=(a0,a1,a2, . . . an−1) ai∈GF(2)   (2)
Multiplication of two elements of GF(2n) is performed by polynomial multiplication of α followed by a modulo operation with the help of the defining polynomial. Addition of two elements of GF(2n) is performed by polynomial addition of α.
There are three typical representative methods of representing the elements of the finite field GF(2n). These methods are defined by different bases. In a standard representation, the elements of the finite field GF(2n) are represented with a standard basis (or polynomial basis) {1, α, α2, α3, . . . , αn−1}. In addition, there are a dual basis and a normal basis.
Formula (3) defines two bases {βi} and {γj} which are dual to each other.Tr(δβiγj)=0(i≠j), 1(i=j), δ∈GF(2n)   (3)
In other words, each of the two bases {β0, β1, β2, . . . , βn−} and {γ0, γ1, γ2, . . . , γn−1} satisfying Formula (3) is a dual basis of the other with respect to Tr(δ·).
When a subset {β, β2, β4, β8, . . . , β2−n} of GF(2n) is a basis, the basis is called a normal basis.
The complexity of a logic circuit required for arithmetic in GF(2n) essentially depends on a particular method by which the elements of a finite field are represented. Representative finite field multipliers are a “dual basis multiplier,” a “normal basis multiplier,” and a “standard basis multiplier”. A dual basis multiplier can be implemented using a linear feedback shift register and is known as requiring a least chip area if basis conversion is excluded. Finite field arithmetic using a normal basis is very efficient for division, square calculation, and exponential calculation, but reduction of a chip area for high degrees is desired. Generally, a standard basis multiplier does not require basis conversion and is easier in terms of extension to a higher-degree finite field and design compared to dual and normal basis multipliers.
Extension to a higher-degree finite field is more difficult in a dual basis multiplier than in a standard basis multiplier because of the complexity of a basis conversion matrix. The present invention provides a basis conversion matrix and method for a dual basis multiplier.
The following description concerns an algorithm performed by a dual basis multiplier.
Let's assume that a polynomial Xn+Xk(s)+Xk(s−1)+ . . . +Xk(1)+1 is a defining polynomial of GF(2n), A and B are elements of GF(2n), and a basis {β0, β1, β2, . . . , βn−1} is a dual basis of a standard basis {1, α, α2, α3, . . . , αn−1}. A matrix Dsd is for standard representation to dual representation conversion, and a matrix Dds is for dual representation to standard representation conversion. In order to calculate a multiplication C=AB, a case where both input and output are dual representations and a case where both input and output are standard representations will be described.
Firstly, the case where both input and output are dual representations, as shown in Formula (4), will be described.A=a0β0+a1β1+a2β2+ . . . +an−1βn−1=(a0,a1,a2, . . . , an−1)B=b0β0+b1β1+b2β2+ . . . +bn−1βn−1=(b0,b1,b2, . . . , bn−1)   (4)
According to the algorithm of the dual basis multiplier, basis conversion is performed even if an input is a dual representation. After obtaining DdsB by performing basis conversion on an input element B, matrix calculation C=MDdsB is performed. Here, a matrix M is defined by Formula (5).
                    M        =                  (                                                                      a                  0                                                                              a                  1                                                                              a                  2                                                            ⋯                                                              a                                      n                    -                    2                                                                                                a                                      n                    -                    1                                                                                                                        a                  1                                                                              a                  2                                                                              a                  3                                                            ⋯                                                              a                                      n                    -                    1                                                                                                a                  n                                                                                                      a                  2                                                                              a                  3                                                                              a                  4                                                            ⋯                                                              a                  n                                                                              a                                      n                    +                    1                                                                                                      ⋮                                            ⋮                                            ⋮                                            ⋰                                            ⋮                                            ⋮                                                                                      a                                      n                    -                    1                                                                                                a                  n                                                                              a                                      n                    +                    1                                                                              ⋯                                                              a                                                            2                      ⁢                      n                                        -                    3                                                                                                a                                                            2                      ⁢                      n                                        -                    2                                                                                )                                    (        5        )            
Here, an+i=ai+ai+k(1)+ai+k(2)+ai+k(3)+ . . . +ai+k(s) (i≧0).
Next, the case where both input and output are standard representations, as shown in Formula (6), will be described.A=a0α0+a1α1+a2α2+ . . . +an−1αn−1=(a0,a1,a2, . . . , an−1)B=b0α0+b1α1+b2α2+ . . . +bn−1αn−1=(b0,b1,b2, . . . , bn−1)   (6)
In this case, the calculation is a little more complicated. In the dual basis multiplier, a standard representation is converted into a dual representation. In other words, DsdA expressed by Formula (7) is obtained by performing basis conversion using the basis conversion matrix Dsd.(a0′, a1′, a2′, . . . , an−1′)=DsdA   (7)
Next, a matrix M expressed by Formula (8) is obtained based on DsdA.
                    M        =                  (                                                                      a                  0                  ′                                                                              a                  1                  ′                                                                              a                  2                  ′                                                            ⋯                                                              a                                      n                    -                    2                                    ′                                                                              a                                      n                    -                    1                                    ′                                                                                                      a                  1                  ′                                                                              a                  2                  ′                                                                              a                  3                  ′                                                            ⋯                                                              a                                      n                    -                    1                                    ′                                                                              a                  n                  ′                                                                                                      a                  2                  ′                                                                              a                  3                  ′                                                                              a                  4                  ′                                                            ⋯                                                              a                  n                  ′                                                                              a                                      n                    +                    1                                    ′                                                                                    ⋮                                            ⋮                                            ⋮                                            ⋰                                            ⋮                                            ⋮                                                                                      a                                      n                    -                    1                                    ′                                                                              a                  n                  ′                                                                              a                                      n                    +                    1                                    ′                                                            ⋯                                                              a                                                            2                      ⁢                      n                                        -                    3                                    ′                                                                              a                                                            2                      ⁢                      n                                        -                    2                                    ′                                                              )                                    (        8        )            
Here, a′n+i=a′i+a′i+k(1)+a′i+k(2)+a′i+k(3)+ . . . +a′i+k(s) (i≧0).
Next, a dual representation MB is obtained using a matrix calculation. The output C, i.e., the result of multiplication, must be a dual representation, so C=DdsMB is obtained using the basis conversion matrix Dds.
Basis conversion is performed by multiplying the basis conversion matrix Dsd or Dds by a vector (an element of a finite field). For every basis conversion in a dual basis multiplier, except for some particular one, the complexity of a basis conversion matrix is very high. In addition, for every basis conversion in a dual basis multiplier, extension to a higher-degree finite field and design is very difficult.
There are three conventional techniques relating to basis conversion, which are simply described below.
The first conventional technique relating to an efficient basis conversion matrix for a particular degree provides a matrix defined by Formula (9) in order to convert a dual representation of a particular degree “n” to a standard representation.
                              D                      d            ⁢                                                  ⁢            s                          =                              (                                                            1                                                  1                                                  0                                                  0                                                  ⋯                                                  0                                                  0                                                  0                                                                              0                                                  1                                                  0                                                  0                                                  ⋯                                                  0                                                  0                                                  1                                                                              0                                                  1                                                  0                                                  0                                                  ⋯                                                  0                                                  1                                                  0                                                                              0                                                  1                                                  0                                                  0                                                  ⋯                                                  1                                                  0                                                  0                                                                              ⋮                                                  ⋮                                                  ⋮                                                  ⋮                                                  ⋰                                                  ⋮                                                  ⋮                                                  ⋮                                                                              0                                                  1                                                  1                                                  0                                                  ⋯                                                  0                                                  0                                                  0                                                                              0                                                  0                                                  0                                                  0                                                  ⋯                                                  0                                                  0                                                  0                                                      )                                              (                              n                +                1                            )                        ×                          (                              n                +                1                            )                                                          (        9        )            
Here Dds is a basis conversion matrix composed of 2n number of 1s. Since the size of the matrix Dds is n+1, the size of all matrices C, M, and B in an arithmetic operation C=MDdsB must be adjusted to n+1. The matrix C has a form (c0, c1, c2, . . . , cn−1, c), and its final output is (c0, c1, c2, . . . , cn−1). The matrix Bis (b0, b1, b2, . . . , bn−1, s[B]), and the matrix M is expressed by Formula (10).
                    M        =                  (                                                                      a                  0                                                                              a                  1                                                                              a                  2                                                            ⋯                                                              a                                      n                    -                    2                                                                                                a                                      n                    -                    1                                                                                                s                  ⁡                                      [                    A                    ]                                                                                                                        a                  1                                                                              a                  2                                                                              a                  3                                                            ⋯                                                              a                                      n                    -                    1                                                                                                s                  ⁡                                      [                    A                    ]                                                                                                a                  0                                                                                                      a                  2                                                                              a                  3                                                                              a                  4                                                            ⋯                                                              s                  ⁡                                      [                    A                    ]                                                                                                a                  0                                                                              a                  1                                                                                    ⋮                                            ⋮                                            ⋮                                            ⋰                                            ⋮                                            ⋮                                            ⋮                                                                                      a                                      n                    -                    1                                                                                                s                  ⁡                                      [                    A                    ]                                                                                                a                  0                                                            ⋯                                                              a                                      n                    -                    4                                                                                                a                                      n                    -                    3                                                                                                a                                      n                    -                    2                                                                                                                        s                  ⁡                                      [                    A                    ]                                                                                                a                  0                                                                              a                  1                                                            ⋯                                                              a                                      n                    -                    3                                                                                                a                                      n                    -                    2                                                                                                a                                      n                    -                    1                                                                                )                                    (        10        )            
Here, s[A]=a0+a1+a2+ . . . +an−1. s[B]=b0+b1+b2+ . . . +bn−1.
In the first conventional technique, the particular degrees “n” are used as shown in Formula (11).n=4,10,12,18,28,36,52,58,60,66,82,100,106,130,138, 148,162,172,178,180,196,210,226,268,292, . . .   (11)
A defining polynomial of the particular “n” degree is expressed by Formula (12).
                                          ∑                          i              =              0                        n                    ⁢                                          ⁢                      x            i                          =                              x            n                    +                      x                          n              -              1                                +                      x                          n              -              2                                +          …          +          x          +          1                                    (        12        )            
By providing a matrix M′ expressed by Formula (13) in C=MDdsB=BM′, the first conventional technique provides an efficient dual basis multiplier, which removes basis conversion.
                              M          ′                =                  (                                                                      a                  0                                                                              a                  1                                                                              a                  2                                                            ⋯                                                              a                                      n                    -                    1                                                                                                s                  ⁡                                      [                    A                    ]                                                                                                                        s                  ⁡                                      [                    A                    ]                                                                                                a                  0                                                                              a                  1                                                            ⋯                                                              a                                      n                    -                    2                                                                                                a                                      n                    -                    1                                                                                                                        a                                      n                    -                    1                                                                                                s                  ⁡                                      [                    A                    ]                                                                                                a                  0                                                            ⋯                                                              a                                      n                    -                    3                                                                                                a                                      n                    -                    2                                                                                                      ⋮                                            ⋮                                            ⋮                                            ⋰                                            ⋮                                            ⋮                                                                                      a                  2                                                                              a                  3                                                                              a                  4                                                            ⋯                                                              a                  0                                                                              a                  1                                                                                                      a                  1                                                                              a                  2                                                                              a                  3                                                                                                                                                            s                  ⁡                                      [                    A                    ]                                                                                                a                  0                                                              )                                    (        13        )            
However, as shown in Formula (11), the first conventional technique is restricted to the particular degrees and uses a defining polynomial having a particular form expressed by Formula (12) rather than a general form. Conversely, the present invention provides a method which is not restricted to particular degrees and is applied to a defining polynomial, i.e., a pentanomial, having a general form.
The second conventional technique relating to an efficient basis conversion matrix for a particular defining polynomial provides a basis conversion matrix, which is simple and easily expandable in a finite field GF(2n) using a defining polynomial having a particular form. The second conventional technique provides a basis conversion matrix for a case where a defining polynomial is a trinomial expressed by Formula (14) and a basis conversion matrix for a case where a defining polynomial is a pentanomial expressed by Formula (15).xn+xk+1   (14)xn+xk+2+xk+1+xk+1   (15)
When the defining polynomial is a trinomial having a particular form expressed by Formula (14), basis conversion matrices Dds and Dsd are express by Formula (16).
                              D                      d            ⁢                                                  ⁢            s                          =                              D                          s              ⁢                                                          ⁢              d                                =                      (                                                                                                      (                                                                                                    0                                                                                ⋯                                                                                1                                                                                                                                ⋮                                                                                ⋰                                                                                ⋮                                                                                                                                1                                                                                ⋯                                                                                0                                                                                              )                                                              k                      ×                      k                                                                                        0                                                                              0                                                                                            (                                                                                                    0                                                                                0                                                                                ⋯                                                                                0                                                                                1                                                                                                                                0                                                                                0                                                                                ⋯                                                                                1                                                                                0                                                                                                                                ⋮                                                                                ⋮                                                                                ⋰                                                                                ⋮                                                                                ⋮                                                                                                                                0                                                                                1                                                                                ⋯                                                                                0                                                                                0                                                                                                                                1                                                                                0                                                                                ⋯                                                                                0                                                                                0                                                                                              )                                                                                      (                                                  n                          -                          k                                                )                                            ×                                              (                                                  n                          -                          k                                                )                                                                                                                  )                                              (        16        )            
That is, each of the basis conversion matrices Dds and Dsd is an n×n matrix and composed of “n” number of 1s.
When the defining polynomial is a pentanomial having a particular form expressed by Formula (15), the basis conversion matrices Dds and Dsd are respectively expressed by Formulae (17) and (18).
                              D                      s            ⁢                                                  ⁢            d                          =                  (                                                                                          (                                                                                            1                                                                          ⋯                                                                          0                                                                          1                                                                                                                      0                                                                          ⋯                                                                          1                                                                          0                                                                                                                      ⋮                                                                          ⋰                                                                          ⋮                                                                          ⋮                                                                                                                      1                                                                          ⋯                                                                          0                                                                          0                                                                                      )                                                                              (                                              k                        +                        1                                            )                                        ×                                          (                                              k                        +                        1                                            )                                                                                                  0                                                                    0                                                                                  (                                                                                            0                                                                          0                                                                          0                                                                          ⋯                                                                          0                                                                          0                                                                          1                                                                                                                      0                                                                          0                                                                          0                                                                          ⋯                                                                          0                                                                          1                                                                          0                                                                                                                      0                                                                          0                                                                          0                                                                          ⋯                                                                          1                                                                          0                                                                          0                                                                                                                      ⋮                                                                          ⋮                                                                          ⋮                                                                          ⋰                                                                          ⋮                                                                          ⋮                                                                          ⋮                                                                                                                      0                                                                          0                                                                          1                                                                          ⋯                                                                          0                                                                          0                                                                          0                                                                                                                      0                                                                          1                                                                          0                                                                          ⋯                                                                          0                                                                          0                                                                          0                                                                                                                      1                                                                          0                                                                          0                                                                          ⋯                                                                          0                                                                          0                                                                          1                                                                                      )                                                                              (                                              n                        -                        k                        -                        1                                            )                                        ×                                          (                                              n                        -                        k                        -                        1                                            )                                                                                                    )                                    (        17        )                                          D                      d            ⁢                                                  ⁢            s                          =                  (                                                                                          (                                                                                            0                                                                          ⋯                                                                          0                                                                          1                                                                                                                      0                                                                          ⋯                                                                          1                                                                          0                                                                                                                      ⋮                                                                          ⋰                                                                          ⋮                                                                          ⋮                                                                                                                      1                                                                          ⋯                                                                          0                                                                          1                                                                                      )                                                                              (                                              k                        +                        1                                            )                                        ×                                          (                                              k                        +                        1                                            )                                                                                                  0                                                                    0                                                                                  (                                                                                            1                                                                          0                                                                          0                                                                          ⋯                                                                          0                                                                          0                                                                          1                                                                                                                      0                                                                          0                                                                          0                                                                          ⋯                                                                          0                                                                          1                                                                          0                                                                                                                      0                                                                          0                                                                          0                                                                          ⋯                                                                          1                                                                          0                                                                          0                                                                                                                      ⋮                                                                          ⋮                                                                          ⋮                                                                          ⋰                                                                          ⋮                                                                          ⋮                                                                          ⋮                                                                                                                      0                                                                          0                                                                          1                                                                          ⋯                                                                          0                                                                          0                                                                          0                                                                                                                      0                                                                          1                                                                          0                                                                          ⋯                                                                          0                                                                          0                                                                          0                                                                                                                      1                                                                          0                                                                          0                                                                          ⋯                                                                          0                                                                          0                                                                          0                                                                                      )                                                                              (                                              n                        -                        k                        -                        1                                            )                                        ×                                          (                                              n                        -                        k                        -                        1                                            )                                                                                                    )                                    (        18        )            
That is, each of the basis conversion matrices Dds and Dsd is an n×n matrix and composed of n+2 number of 1s.
Since a trinomial or pentanomial is usually used as a defining polynomial in finite fields used in practical applications, the basis conversion matrices provided by the second conventional technique are very useful. However, these basis conversion matrices can be used for the trinomial and the pentanomial respectively having a particular form expressed by Formulae (14) and (15), but cannot be used for a pentanomial having a general form. However, the present invention provides a basis conversion matrix and method for a polynomial having a general form.
The third conventional technique relating to a method of calculating a basis conversion matrix provides a method of calculating a basis conversion matrix in an arbitrary finite field GF(2n). Here, {1, α, α2, . . . , αn−1} is a standard basis of GF(2n), and a defining polynomial is expressed by Formula (19).f(x)=xn+xk(s)+xk(s−1)+ . . . +xk(1)+1   (19)
After obtaining β, as shown in Formula (20), a basis conversion matrix Dds for converting a dual representation to a standard representation is obtained using Formula (21).β=(f′(α)αhu nt)−1, t=[s/2]  (20)
                              D                      d            ⁢                                                  ⁢            s                          =                  (                                                                      T                  ⁢                                                                          ⁢                                      r                    ⁡                                          (                                              β                        ·                                                  α                          0                                                                    )                                                                                                                    T                  ⁢                                                                          ⁢                                      r                    ⁡                                          (                                              β                        ·                                                  α                          1                                                                    )                                                                                                  ⋯                                                              T                  ⁢                                                                          ⁢                                      r                    ⁡                                          (                                              β                        ·                                                  α                                                      n                            -                            1                                                                                              )                                                                                                                                            T                  ⁢                                                                          ⁢                                      r                    ⁡                                          (                                              β                        ·                                                  α                          1                                                                    )                                                                                                                    T                  ⁢                                                                          ⁢                                      r                    ⁡                                          (                                              β                        ·                                                  α                          2                                                                    )                                                                                                  ⋯                                                              T                  ⁢                                                                          ⁢                                      r                    ⁡                                          (                                              β                        ·                                                  α                          n                                                                    )                                                                                                                          ⋮                                            ⋮                                            ⋰                                            ⋮                                                                                      T                  ⁢                                                                          ⁢                                      r                    ⁡                                          (                                              β                        ·                                                  α                                                      n                            -                            1                                                                                              )                                                                                                                    T                  ⁢                                                                          ⁢                                      r                    ⁡                                          (                                              β                        ·                                                  α                          n                                                                    )                                                                                                  ⋯                                                              T                  ⁢                                                                          ⁢                                      r                    ⁡                                          (                                              β                        ·                                                  α                                                                                    2                              ⁢                              n                                                        -                            2                                                                                              )                                                                                                    )                                    (        21        )            
However, since β is generated using a nonlinear method to k(i), the basis conversion matrix Dds cannot be easily represented with respect to k(i). In addition, the basis conversion matrix Dds is made without considering the complexity of its inverse matrix Dsd, so the inverse matrix Dsd may be very complex in some cases. However, the present invention provides a basis conversion matrix Dsd selected using a linear method to k(i) and basis conversion matrices Dds and Dsd, which are easily defined by k(i), when the defining polynomial is a pentanomial.